--[[
    优先队列 priority_queue
    用完全二叉树的大小堆实现

    1.清空队列
    2.入队
    3.出队
    4.取节点个数
    优先级越大的先插入到队列头，这样优先级大的先出队列

    --用完全二叉树的大小堆实现更好

    node = {
        id 作为大小比较值
    }
--]]


local Heap = require("heap")


local table_insert = table.insert
local table_remove = table.remove

local PQueue = {}

function PQueue.new(...)
    local instance = setmetatable({}, {__index=PQueue})
    instance:ctor(...)
    return instance
end

function PQueue:ctor()
    self.heap = Heap.new()
    self.nodes = {} --用于存放数据
end

--
function PQueue:push(node)
    table_insert(self.nodes, node)
    self.heap:maxHeap(self.nodes) --生成大顶堆
    return
end

--优先取id值大的node
function PQueue:pop()
    if not self.nodes or not self.nodes[1] then
        return
    end

    local value = self.nodes[1]
    table_remove(self.nodes, 1)
    return value
end

function PQueue:getTop()
    return self.nodes[1]
end

function PQueue:getNodes()
    return self.nodes
end

function PQueue:print()
    for i = 1, #self.nodes do
        print(i, self.nodes[i].id)
    end
end

function PQueue:size()
    return #self.nodes
end

function PQueue:clear()
    self.nodes = {} --用于存放数据
end

function PQueue:empty()
    if #self.nodes > 0 then
        return true
    end
    return false
end


------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "pqueue2.lua" then
    local start_time = os.time()
    print("_______", start_time)
    local queue = PQueue.new()
    for i=1, 10000 do
        queue:push({id=math.random(1, 100000)})
    end
    --queue:print()
    print("_______", os.time() - start_time)

    while queue:empty() do
        queue:pop()
    end
    --local a = queue:pop()
    --local b = queue:pop()
    --print("pop:", a.id, b.id)
    print("_______", os.time() - start_time)
    --queue:print()

end

return PQueue